ABC147 C - HonestOrUnkind2
https://gyazo.com/55f381c019ec514e0c30f27bd7506c0a
問題
感想
問題の理解、実装ともに難しく感じた
解説読まないと解けなかった
問題の整理に、紙なりホワイトボードなりを使うのがいいかもしれない
解説
解説PDF読んでも何となくしかわからなかった
N 人の人がそれぞれ正直者であるか不親切な人であるかを決めれば, その状態が証言と矛盾しないかは, $ O(N^2)で容易に確かめることが出来ます.
N 人の人がそれぞれ正直者か否かについては全部で$ 2^N通りしかありませんから, これら全ての場合について矛盾が生じないかを調べ, 矛盾が生じないうちでの正直者の最多人数を答えとすれば良いです.
YouTubeの解説見たらよくわかった
https://www.youtube.com/watch?v=tNyPYIhy9Ms&t=3832s
矛盾がない条件
不親切な人の証言は何でもよい
正直者の証言がすべて正しい
すべての人が正直者 or 不親切な人であるパターンをbit全探索する すべての正直者の証言に矛盾がないパターンのなかで、正直者の最多人数を答えとする
実装
はじめは、ライブラリを用いずにbit演算で解いた
itertools.productを使って書き直した
1年半空けて解き直した
自力でできたけど、時間がかかった